#pragma once
#include <iostream>

template <class T>
class ListNode
{
public:
	ListNode(T data = T())
		:_next(nullptr), _prev(nullptr), _data(data)
	{}
public:
	ListNode<T>* _next;
	ListNode<T>* _prev;
	T _data;
};


template <class T>
class List
{
public:
	List()
		:phead(new ListNode<T>())
	{
		phead->_next = phead;
		phead->_prev = phead;
	}

	~List()
	{
		ListNode<T>* cur = phead->_next;
		while (cur != phead)
		{
			ListNode<T>* temp = cur->_next;
			cur = temp->_next;
			delete temp;
		}
		delete phead;
	}

	void Print()
	{
		ListNode<T>* cur = phead->_next;
		while (cur != phead)
		{
			std::cout << cur->_data << " ";
			cur = cur->_next;
		}
		std::cout << std::endl;
	}
public:
	void PushBack(T x)
	{
		ListNode<T>* tail = phead->_prev;
		ListNode<T>* node = new ListNode<T>(x);

		phead->_prev = node;
		node->_next = phead;
		tail->_next = node;
		node->_prev = tail;
	}

	void PopBack()
	{
		if (phead->_prev != phead)
		{
			ListNode<T>* del = phead->_prev;
			ListNode<T>* tail = del->_prev;
			phead->_prev = tail;
			tail->_next = phead;
			delete del;
		}
	}

	void Pushfront(T x)
	{
		ListNode<T>* next = phead->_next;
		ListNode<T>* node = new ListNode<T>(x);
		phead->_next = node;
		node->_prev = phead;
		node->_next = next;
		next->_prev = node;
	}

	void Popfront()
	{
		if (phead->_next != phead)
		{
			ListNode<T>* del = phead->_next;
			ListNode<T>* next = del->_next;
			phead->_next = next;
			next->_prev = phead;
			delete del;
		}
	}
private:
	ListNode<T>* phead;
};